发布于 

[学习笔记]AC自动机

[学习笔记]AC自动机

这么长时间，总该学点新东西。打算新开这么一个"系列"，放一些新学的算法和数据结构。毕竟大学已经一年了，却没有在算法上继续扩宽自己的知识面，比赛时明显能感到自己知识广度的不足。

介绍

AC自动机，全称是Aho-Corasick automaton，于1975年产生于贝尔实验室，是著名的多模式匹配算法。其主要是Trie (字典树) 和KMP算法的结合，能够找出在一个母串中多个子串的出现次数。

与KMP算法相同，其对时间的加速主要取决于失配函数。但是由于我们要实现多模式匹配，所以这里的匹配函数要针对一个Trie 树构建而非一个数组。由于每次匹配失败后我们不会重新匹配，而是根据失配函数进行跳跃，所以可以在极端情况下节省大量的时间。

流程及原理

AC自动机的实现流程可以分为几步：Trie树的构建；失配函数的生成；进行匹配。与KMP算法一样，失配函数的生成是其中最核心也是最困难的部分。

Trie树的构建

首先，我们假设我们有一个母串"ourshers",然后我们需要匹配子串"our","ours","he"， "him","she","hers"在其中出现的总次数。因为很明显，这几个子串并没有一个公共的首字母，而我们需要将所有的串放入到一个树中，所以我们要将root节点设为空，然后在root节点的线面连接每一个单词的首字母作为子节点。最后我们生成的Trie树应该如下图所示：

Trie树

其中，用正方形圈起来的是单词的结尾。

失配函数的生成

在实现AC自动机的失配函数之前，可以先回顾一下KMP算法的失配函数。假如失配函数是f[],字符数组a[]是我们想要生成失配函数的母串，那么代码如下：

1
2
3
4
5
6
7
for (int i= 0; i<m; i++)
{
trueint j = f[i];
    while (j && a[i]!=a[j])
    	j = f[j];
    f[i+1] = a[i]==a[j]? j+1 : 0;
}

我们通过不断地将当前点根据失配函数向前回溯，找到可以相同的点，来构造出下一个点的失配函数。注意，这里的失配函数满足的是\(a[i-1]==a[f[i]-1]\),即失配函数会从无法匹配的字符直接跳向需要进行下一步匹配的字符。

那么，现在我们便来考虑AC自动机的失配函数。其思想和KMP类似，只不过这次我们需要用BFS来实现。在这里，我们将构建一个结构体，包含word(char),fail(node*),son(node*[]),next(Node*),isWrod(bool)三个成员变量(word主要用来debug，实际不一定用到)。

代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
queue<Node*> q;
root->fail = NULL;
while(!q.empty())
{
trueNode* v = q.front();
    q.pop();
true
    for (int i = 0; i<26; i++)
true{
    	Node *&c = v->c[i];
        
    	if (!c)    continue;
        
    	Node *u = v->fail; 
    	while ( u!=root && !u->c[i] )
        	u = u->fail;
            
    	c->fail = v!=root && u->c[i]? u->c[i] : root;
    	c->next = c->fail-isWord ? c->fail : c->fail->next;
        
    	q.push(c);
true}
}

这样的话，我们就能够得到失配函数fail。注意，这里的fail满足的条件是t->word==t->fail->word。isWord记录当前是否为词尾。而next的作用是记录最近的为词尾的当前节点的失配节点。

在完成了处理之后，我们便能够得到一个如下图的情况：

Fail-Trie

模式匹配

匹配时整体思路与构建失配函数类似。我们假设母串为s(string类型)。所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node *v = root;
for (int i = 0; i<s.length(); i++)
{
truechar ch = s[i];
truewhile ( v!=root && !v->c[ch-‘a’])
    	v = v->fail;
truev = v->c[ch-‘a’]? V->c[ch-‘a’] : root;

trueNode* t;
trueif (v->isWord)
        t = v;
    else t = v->next;
        while (t)
        {
            ans ++;
            t = t->next;
        }
}

我们首先找到当前节点是否可以继续走下去。若是不可以，则回溯fail指针，找到第一个可以匹配的点。然后我们再判断该点是否为词尾，并且通过next指针判断其是否为其他单词的词尾。

这样，我们便完成了匹配部分。此时AC自动机的大部分功能便已经实现了。

例题

先列在这里，日后再写

Luogu 3808

题目来源: Luogu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
truechar word;		//record the word
trueint cnt;		//record if this word is the end of some word, and how many is it
trueNode *fail;
trueNode *next;
trueNode *son[26];

trueNode(char word=' '):word(word)
true{
truetruefail = NULL;
truetruenext = NULL;
truetruecnt = 0;

truetruefor (int i = 0; i<26; i++)
truetruetrueson[i] = NULL;
true}
};

struct Trie
{
trueNode *root;

trueTrie(vector<string> s){
truetrueroot = new Node();

truetruefor (int i = 0; i<s.size(); i++)
truetruetruebuild(s[i]);
true}

truevoid build(const string &s)
	{
truetrueint i = 0;
truetrueNode *p = root;

truetruewhile (i!=s.length())
truetrue{
truetruetrueif (p->son[s[i]-'a']==NULL)
truetruetruetruep->son[s[i]-'a'] = new Node(s[i]);

truetruetruep = p->son[s[i]-'a'];
truetruetruei++;
truetrue}

truetruep->cnt ++;

truetruereturn;
true}

truevoid makeFail()
	{
truetruequeue<Node*> q;
truetrueq.push(root);
truetruewhile (!q.empty())
truetrue{
truetruetrueNode *v = q.front();
truetruetrueq.pop();

truetruetruefor (int i = 0; i<26; i++)
truetruetrue{
truetruetruetrueNode *&c = v->son[i];

truetruetruetrueif (!c)	continue;

truetruetruetrueNode *u = v->fail;
truetruetruetruewhile ( u && !u->son[i] )
truetruetruetruetrueu = u->fail;

truetruetruetruec->fail = (v!=root && u->son[i])? u->son[i] : root;
truetruetruetruec->next = c->fail->cnt ? c->fail : c->fail->next;

truetruetruetrueq.push(c);
truetruetrue}

truetrue}

truetruereturn;
true}

trueint pair(string m)
	{	
truetrueint ans = 0;

truetrueNode *v = root;
truetruefor (int i = 0; i<m.length(); i++)
truetrue{
truetruetrueconst char &ch = m[i];

truetruetruewhile ( v!=root && !v->son[ch-'a'] )
truetruetruetruev = v->fail;

truetruetruev = v->son[ch-'a']? v->son[ch-'a'] : root;

truetruetrueNode *t = v;
truetruetruewhile (t)
truetruetrue{
truetruetruetrue//	cout <<"* " << i << " " << t << " " << t->word << " " << t->cnt << endl;
truetruetruetrueans += t->cnt;
truetruetruetruet->cnt = 0;
truetruetruetruet = t->next;
truetruetrue}
truetrue}

truetruereturn ans;
true}

};

int n;
vector<string> s;
string m;

int main()
{
truecin >> n;
truefor (int i = 0; i<n; i++)
true{
truetruestring t;
truetruecin >> t;
truetrues.push_back(t);
true}
truecin >> m;

trueTrie* t = new Trie(s);

truet->makeFail();

trueint ans = t->pair(m);

truecout << ans;
}

Luogu 3796

题目来源: Luogu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int ans[200];

struct Node
{
truechar word;		//record the word
trueint cnt;		//record if this word is the end of some word, and how many is it
trueNode *fail;
trueNode *next;
trueNode *son[26];

truevector<int> words; 		//record whose end this node is.

trueNode(Node *p,char word=' '):fail(p),word(word)
true{
truetruenext = NULL;
truetruecnt = 0;

truetruefor (int i = 0; i<26; i++)
truetruetrueson[i] = NULL;
true}

true~Node()
true{
truetruefor (int i = 0; i<26; i++)
truetruetrueif (son[i])
truetruetruetruedelete son[i];
true}
};

struct Trie
{
trueNode *root;

trueTrie(vector<string> s){
truetrueroot = new Node(NULL);
truetrueroot->fail = root;

truetruefor (int i = 0; i<s.size(); i++)
truetruetruebuild(s[i],i);
true}

true~Trie()
true{
truetruedelete root;
true}

truevoid build(const string &s,const int &x)
	{
truetrueint i = 0;
truetrueNode *p = root;

truetruewhile (i!=s.length())
truetrue{
truetruetrueif (p->son[s[i]-'a']==NULL)
truetruetruetruep->son[s[i]-'a'] = new Node(root,s[i]);

truetruetruep = p->son[s[i]-'a'];
truetruetruei++;
truetrue}

truetruep->cnt ++;
truetruep->words.push_back(x);

truetruereturn;
true}

truevoid makeFail()
	{
truetruequeue<Node*> q;
truetrueq.push(root);
truetruewhile (!q.empty())
truetrue{
truetruetrueNode *v = q.front();
truetruetrueq.pop();

truetruetruefor (int i = 0; i<26; i++)
truetruetrue{
truetruetruetrueNode *&c = v->son[i];

truetruetruetrueif (!c)	continue;

truetruetruetrueNode *u = v->fail;
truetruetruetruewhile ( u!=root && !u->son[i] )
truetruetruetrue{
truetruetruetruetrueu = u->fail;
truetruetruetrue}

truetruetruetruec->fail = (v!=root && u->son[i])? u->son[i] : root;
truetruetruetruec->next = c->fail->cnt ? c->fail : c->fail->next;

truetruetruetrueq.push(c);

truetruetrue}
truetrue}

truetruereturn;
true}

truevoid pair(string m)
	{
truetrueNode *v = root;
truetruefor (int i = 0; i<m.length(); i++)
truetrue{
truetruetrueconst char &ch = m[i];

truetruetruewhile ( v!=root && !v->son[ch-'a'] )
truetruetruetruev = v->fail;

truetruetruev = v->son[ch-'a']? v->son[ch-'a'] : root;

truetruetrueNode *t = v;
truetruetruewhile (t)
truetruetrue{
truetruetruetrueif (t->cnt)
truetruetruetrue{
truetruetruetruetruefor (int i = 0; i<t->words.size(); i++)
truetruetruetruetruetrueans[t->words[i]] ++ ;
truetruetruetrue}
truetruetruetruet = t->next;
truetruetrue}
truetrue}

truetruereturn;
true}

};

int n;
vector<string> s;
string m;

int main()
{
truewhile (cin >> n && n)
true{
truetruememset(ans,0,sizeof(ans));
truetrues.clear();

truetruefor (int i = 0; i<n; i++)
truetrue{
truetruetruestring t;
truetruetruecin >> t;
truetruetrues.push_back(t);
truetrue}
truetruecin >> m;
true
truetrueTrie* t = new Trie(s);

truetruet->makeFail();

truetruet->pair(m);

truetrueint maxn = 0;
truetruefor (int i = 0; i<n; i++)
truetruetruemaxn = max(maxn,ans[i]);

truetruecout << maxn << endl;

truetruefor (int i = 0; i<n; i++)
truetruetrueif (maxn==ans[i])
truetruetruetruecout << s[i] << endl;

truetruedelete t;
true}

truereturn 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建，使用 Stellar 作为主题。